package com.hy.stack.monotoneStack;

import java.util.Stack;

public class CatchRainwater {

    /**
     * 42. 接雨水
     * 力扣题目链接
     *
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     *
     * 示例 1：
     * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
     * 输出：6
     * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
     * 示例 2：
     *
     * 输入：height = [4,2,0,3,2,5]
     * 输出：9
     *
     *  思路
     * 接雨水问题在面试中还是常见题目的，有必要好好讲一讲。
     *
     * 本文深度讲解如下三种方法：
     *
     * 双指针法
     * 动态规划
     * 单调栈
     * 双指针解法
     * 这道题目使用双指针法并不简单，我们来看一下思路。
     *
     * 首先要明确，要按照行来计算，还是按照列来计算。
     * 按照列来计算如图： 42.接雨水1
     *
     * 一些同学在实现的时候，很容易一会按照行来计算一会按照列来计算，这样就会越写越乱。
     *
     * 我个人倾向于按照列来计算，比较容易理解，接下来看一下按照列如何计算。
     *
     * 首先，如果按照列来计算的话，宽度一定是1了，我们再把每一列的雨水的高度求出来就可以了。
     *
     * 可以看出每一列雨水的高度，取决于，该列 左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。
     *
     * 这句话可以有点绕，来举一个理解，例如求列4的雨水高度，如图：
     *
     * 列4 左侧最高的柱子是列3，高度为2（以下用lHeight表示）。
     *
     * 列4 右侧最高的柱子是列7，高度为3（以下用rHeight表示）。
     *
     * 列4 柱子的高度为1（以下用height表示）
     *
     * 那么列4的雨水高度为 列3和列7的高度最小值减列4高度，即： min(lHeight, rHeight) - height。
     *
     * 列4的雨水高度求出来了，宽度为1，相乘就是列4的雨水体积了。
     *
     * 此时求出了列4的雨水体积。
     *
     * 一样的方法，只要从头遍历一遍所有的列，然后求出每一列雨水的体积，相加之后就是总雨水的体积了。
     *
     * 首先从头遍历所有的列，并且要注意第一个柱子和最后一个柱子不接雨水，代码如下：
     *
     * for (int i = 0; i < height.size(); i++) {
     *     // 第一个柱子和最后一个柱子不接雨水
     *     if (i == 0 || i == height.size() - 1) continue;
     * }
     * 在for循环中求左右两边最高柱子，代码如下：
     *
     * int rHeight = height[i]; // 记录右边柱子的最高高度
     * int lHeight = height[i]; // 记录左边柱子的最高高度
     * for (int r = i + 1; r < height.size(); r++) {
     *     if (height[r] > rHeight) rHeight = height[r];
     * }
     * for (int l = i - 1; l >= 0; l--) {
     *     if (height[l] > lHeight) lHeight = height[l];
     * }
     * 最后，计算该列的雨水高度，代码如下：
     *
     * int h = min(lHeight, rHeight) - height[i];
     * if (h > 0) sum += h; // 注意只有h大于零的时候，在统计到总和中
     *
     * @param height
     * @return
     */
    // 双指针法
    public static int catchRainwater(int [] height){
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            // 第一个 柱子 不接雨水
            if (i == 0 || i == height.length -1 ){
                continue;
            }
            // 记录 左右 边柱子的最高高度
            int lheight = height[i];
            int rheight = height[i];
            for (int r = i + 1; r < height.length; r++) {
                if (height[r] > rheight ){
                    rheight = height[r];
                }
            }
            for (int l = i - 1; l >= 0; l--) {
                if (height[l] > lheight){
                    lheight = height[l];

                }
            }
            int h = Math.min(lheight,rheight) - height[i];
            if (h > 0){
                sum +=h;
            }
        }
        return sum;
    }

    /**
     * 动态规划
     *  动态规划解法  (纵向计算)
     * 在上一节的双指针解法中，我们可以看到只要记录左边柱子的最高高度 和 右边柱子的最高高度，就可以计算当前位置的雨水面积，这就是通过列来计算。
     *
     * 当前列雨水面积：min(左边柱子的最高高度，记录右边柱子的最高高度) - 当前柱子高度。
     *
     * 为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight）。这样就避免了重复计算，这就用到了动态规划。
     *
     * 当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值。
     *
     * 即从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);
     *
     * 从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);
     *
     * 这样就找到递推公式。
     *
     *  Math.min(maxLeft[i],maxRight[i]) - height[i];
     *
     *
     * @param height
     * @return
     */
    public static int catchRainwater02(int [] height){
        int len = height.length;
        if (len <= 0 ){
            return 0;
        }
        // 记录每个柱子左边柱子最大高度
        int [] maxLeft = new int[len];
        maxLeft[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            maxLeft[i] = Math.max(height[i],maxLeft[i-1]);
        }
        // 记录每个柱子左边柱子最大高度
        int [] maxRight = new int[len];
        maxRight[len - 1] = height[len - 1];
        for (int i = len - 2; i > 0; i--) {
            maxRight[i] = Math.max(height[i],maxRight[i+1]);
        }
        // 求和
        int sum = 0;
        for (int i = 0; i < len; i++) {
         int h = Math.min(maxLeft[i],maxRight[i]) - height[i];
         if (h > 0){
             sum += h;
         }
        }
        return sum;
    }

    /**
     * 单调栈法  (横向计算体积)
     *
     *
     *
     * @param height
     * @return
     */
    public static int catchRainwater03(int [] height){
        int len = height.length;
        if (len <= 0){
            return 0;
        }
        Stack<Integer> st = new Stack<Integer>();
        int sum = 0;
        st.push(0);
        for (int i = 1; i < len; i++) {
            Integer stackTop = st.peek();
            // 栈顶索引  与  数组索引  比较
            if (height[i] < stackTop){
                st.push(i);
            // 因为相等的相邻墙，左边一个是不可能存放雨水的，所以pop左边的index, push当前的index
            }else if (height[i] == stackTop){
                st.pop();
                st.push(i);
            }else {
                //pop up all lower value
               int heightAtIdx = height[i];
               while (!st.isEmpty() && (heightAtIdx > height[stackTop])){
                   int mid = st.pop();
                   if (!st.isEmpty()){
                       Integer left = st.peek();
                       // 计算  高度 (值)
                       int h = Math.min(height[left],height[i]) - height[mid];
                       // 计算  宽度 (索引)
                       int w = i - left - 1;
                       // 计算 体积
                       int hold = h * w;
                       if (hold > 0){
                           sum += hold;
                           // 更新 栈顶元素
                           stackTop = st.peek();
                       }
                   }
               }
               // 添加索引至栈顶
                st.push(i);
            }
        }
        return sum;
    }
    public static void main(String[] args) {
        int [] water = {4,2,0,3,2,5};
        System.out.println("res: "+ catchRainwater(water));
        System.out.println("res: "+ catchRainwater02(water));
        System.out.println("res: "+ catchRainwater03(water));
    }
}
